package leetcode3;
import java.util.*;
/**
 * 设置循环队列
 */
class MyCircularQueue {
    //思路：使用数组+两个指针，一个指向队尾(入)，另一个指向队头(出)
    //预留一个空间，用来判断为满
    int[] elem;
    int front;//头 -- 用来出
    int rear; //尾 -- 用来进

    public MyCircularQueue(int k) {
        elem = new int[k+1];
    }

    public boolean enQueue(int value) {
        //1.判满
        //2.插入
        if(isFull()) return false;
        elem[rear++]=value;
        if(rear==elem.length) rear=0;
        return true;
    }

    public boolean deQueue() {
        //1.判空
        //2.删除
        if(isEmpty()) return false;
        front++;
        if(front==elem.length) front=0;
        return true;
    }

    public int Front() {
        //获取队首元素
        if(isEmpty()) return -1;
        return elem[front];
    }

    public int Rear() {
        //获取队尾元素
        if(isEmpty()) return -1;
        if(rear==0) return elem[elem.length-1];
        else return elem[rear-1];
    }

    public boolean isEmpty() {
        //判空 -- 两个指针相遇时为空
        return front==rear;
    }

    public boolean isFull() {
        //判满 -- 队尾+1 == 队头为满
        return (rear+1)%elem.length == front;
    }
}

/**
 * 使用队列实现栈
 */
class MyStack {

    Queue<Integer> q1;
    Queue<Integer> q2;

    public MyStack() {
        q1 = new LinkedList<>();
        q2 = new LinkedList<>();
    }

    public void push(int x) {
        if(empty()) {
            //都为空，随便进一个
            q1.add(x);
        }else {
            //进栈 -- 进不为空的队列即可
            if(q1.isEmpty()) {
                q2.add(x);
            }else {
                q1.add(x);
            }
        }
    }

    public int pop() {
        //出栈 -- 把队列中的元素倒入空队列，队列剩下最后一个就是要出栈的元素
        if(empty()) return -1;
        if(!q1.isEmpty()) {
            int size = q1.size()-1;
            while(size-- != 0) {
                q2.add(q1.poll());
            }
            return q1.poll();
        }else {
            int size = q2.size()-1;
            while(size-- != 0) {
                q1.add(q2.poll());
            }
            return q2.poll();
        }
    }

    public int top() {
        if(empty()) return -1;
        if(!q1.isEmpty()) {
            int size = q1.size()-1;
            while(size-- != 0) {
                q2.add(q1.poll());
            }
            int tmp = q1.peek();
            q2.add(q1.poll());
            return tmp;
        }else {
            int size = q2.size()-1;
            while(size-- != 0) {
                q1.add(q2.poll());
            }
            int tmp = q2.peek();
            q1.add(q2.poll());
            return tmp;
        }
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}



class MyQueue {

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if(empty()) return -1;
        if(stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if(empty()) return -1;
        if(stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}



public class Day17 {
}
